#include<bits/stdc++.h>
using namespace std;
int a[100][100],n;
int dp[100][100];
int T,best;
int f(int x,int y){
    if(dp[x][y]!=0)return dp[x][y];
    if(x==n-1)return dp[x][y]=a[x][y];
    return dp[x][y]=a[x][y]+max(f(x+1,y),f(x+1,y+1));

}
int main(){
    cin>>T;
    while(T--){
        memset(a,sizeof(a),0);
        memset(dp,sizeof(dp),0);
        cin>>n;
        for(int i=0;i<n;i++)for(int j=0;j<=i;j++)cin>>a[i][j];
        cout<<f(0,0)<<endl;
    }
    return 0;
}

